class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param str string字符串 
     * @return string字符串vector
     */
    vector<string> ret;
    string path;
    bool vis[11] = { false };
    string s;
    int n;
 
    vector<string> Permutation(string str) {  // Day33_3_全排列
        // vector<string> ret;
        // sort(str.begin(), str.end());
        // do
        // {
        //     ret.push_back(str);
        // }while (next_permutation(str.begin(), str.end()));
        // return ret;
        sort(str.begin(), str.end());
        s = str;
        n = s.size();
 
        dfs(0);
        return ret;
    }
 
    void dfs(int pos)
    {
        if(pos == n)
        {
            ret.push_back(path);
            return;
        }
 
        for(int i = 0; i < n; ++i)
        {
            if(vis[i] || (i > 0 && s[i] == s[i - 1] && !vis[i - 1]))
                continue;
            
            path += s[i];
            vis[i] = true;
            dfs(pos + 1);
            
            vis[i] = false;
            path.pop_back();
        }
    }
};